package nth.bananas.solving;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

import nth.bananas.game.Player;

public class BruteForceSolver implements Solver {

	private Player p;

	public BruteForceSolver(Player p) {
		this.p = p;
	}

	@Override
	public Set<Puzzle> solve(Puzzle start) {
		start.fillOutEmptyBoard();
		Set<Puzzle> possibleSolutions = new HashSet<Puzzle>();
		possibleSolutions.addAll(continuousPaths(start.totalFreePieces(), start));

		Set<Puzzle> withTiles = possibleTilePlacement(possibleSolutions); 

		withTiles.removeAll(invalidSolutions(withTiles));

		return withTiles;
	}

	private Set<Puzzle> possibleTilePlacement(Set<Puzzle> possibleSolutions) {
		Set<Puzzle> result = new HashSet<Puzzle>();

		for (Puzzle p : possibleSolutions) {
			result.addAll(filledPuzzlePermutations(p));
		}

		return result;
	}

	public Set<Puzzle> filledPuzzlePermutations(Puzzle p) {
		assert p.totalFreePieces() == p.countOnBoard(null) : String.format("There should be an equal number of free pieces and open spaces, but instead it's free: %d, open %d", p.totalFreePieces(), p.countOnBoard(null));
		Set<Puzzle> result = new HashSet<Puzzle>();

		if (p.totalFreePieces() == 1) {
			GridSpot<Letter> only = null;
			for (GridSpot<Letter> gs : p.getSpots()) {
				if (gs.content() == null) {
					only = gs;
					break;
				}
			}
			
			Puzzle filled = p.fromFreeToTiles(only, p.getRandomTile());
			result.add(filled);
			return result;
		}
		
		Puzzle perm;
		Set<Letter> freeLetters;
		int pFreeCount = p.freeLetters().size();
		for (GridSpot<Letter> gs : p.getSpots()) {
			if (gs.content() == null) { // if this tile is empty
				freeLetters = new HashSet<Letter>(p.freeLetters());
				for (Letter t : freeLetters) {
					perm = p.fromFreeToTiles(gs, t);
					assert pFreeCount == perm.freeLetters().size() + 1 : String.format("The new puzzle should have 1 less tile than the old, but instead it's old: %d, new %d.", pFreeCount, perm.freeLetters().size()); 
					result.addAll(filledPuzzlePermutations(perm));
				}
			}
		}
		
		for (Puzzle ans : result) {
			for (GridSpot<Letter> gs : ans.getSpots()) {
				assert gs.content() != null : String.format("No puzzle should contain an empty spot, but this one does: %s", ans);
			}
		}

		return result;
	}

	private Collection<?> invalidSolutions(Set<Puzzle> possibleSolutions) {
		Set<Puzzle> invalids = new HashSet<Puzzle>();

		for (Puzzle p : possibleSolutions) {
			if (! PuzzleRules.isValid(p)) {
				invalids.add(p);
			}
		}

		return invalids;
	}

	/**
	 * Finds every placement of <code>t</code> tiles onto <code>grid</code>
	 * such that each piece is sharing a corner with at least one other piece.
	 * 
	 * @param t		the number of tiles to place in the puzzle
	 * @param grid	the grid in which to place the tiles
	 * @return		a set of puzzles with all the pieces in a continuous path
	 */
	private Set<Puzzle> continuousPaths(final int t, final Puzzle grid) {
		Set<Puzzle> result = new HashSet<Puzzle>();

		if (t == 1) {
			result.add(grid);
			return result;
		}

		Puzzle start;
		Puzzle subGrid;
		Set<GridSpot<Letter>> startSpots = new HashSet<GridSpot<Letter>>();;
		Collection<Puzzle> solutionsWithSpot = new HashSet<Puzzle>();
		for (GridSpot<Letter> spot : grid.getSpots()) {
			startSpots.addAll(grid.adjacentTo(spot));
			subGrid = grid.copyWithoutSpot(spot);

			solutionsWithSpot = contPathsRec(t - 1, subGrid, startSpots);

			start = subGrid.inverse();

			assert start.getSpot(spot.getX(), spot.getY()).equals(spot);

			for (Puzzle p : solutionsWithSpot) {
				Puzzle inverse = p.inverse();
				Puzzle gridUnion = start.gridUnion(inverse); // is grid union at all necessary?
				result.add(gridUnion); 
			}


			startSpots.clear();
		}

		return result;	
	}

	/**
	 * 
	 * @param t
	 * @param subGrid		must be empty
	 * @param startSpots
	 * @return
	 */
	private Collection<Puzzle> contPathsRec(final int t, final Puzzle subGrid, final Set<GridSpot<Letter>> startSpots) {
		Set<Puzzle> result = new HashSet<Puzzle>();

		if (t == 1) {
			for (GridSpot<Letter> ps : startSpots) {
				result.add(subGrid.copyWithoutSpot(ps));
			}
			return result;
		}

		Puzzle nextSubGrid;
		Set<GridSpot<Letter>> nextStartSpots = new HashSet<GridSpot<Letter>>();;
		for (GridSpot<Letter> spot : startSpots) {
			nextStartSpots.addAll(subGrid.adjacentTo(spot));
			nextSubGrid = subGrid.copyWithoutSpot(spot);
			result.addAll(contPathsRec(t - 1, nextSubGrid, nextStartSpots));
			nextStartSpots.clear();
		}

		return result;
	}



}
